type Item = {
    value: number;
    left?: Item;
    right?: Item;
}
class Tree {
    constructor(
        public value: number,
        public children: Tree[]) { }
}

function eachTree(tree: Item) {
    let queue = [tree];
    while (queue.length) {
        const { value, left, right } = queue.shift()!;
        console.log(value);
        if (left) {
            queue.push(left)
        }
        if (right) {
            queue.push(right)
        }
    }
}
function eachTree2(tree: Item) {
    let queue = [tree];
    let count = 0;
    while (queue.length) {
        console.log('广度--', count);
        const len = queue.length;
        for (let i = 0; i < len; i++) {
            const { value, left, right } = queue.shift()!;
            console.log(value);
            if (left) queue.push(left);
            if (right) queue.push(right);
        }
        count++;
    }
}
// 深度
function transtree(root?: Item) {
    if (!root) return;
    // 先序
    transtree(root.left);
    // 中序
    transtree(root.right);
    // 后序
}
// function aaa(l1:number[],l2:number[]){

//     let obj:Item = {value:0}
//     const val = l1[0];
//     const index = l2.findIndex(v=>v===val)!+1;
//     obj.value = val;
//     const leftArr1 = l1.slice(0,index);
//     const leftAr2 = l2.slice(0,index);
//     obj.left = aaa(leftArr1,leftAr2)
//     obj.right = aaa(l1.slice(index),l2.slice(index))
//     return obj;
// }

//  Definition for a binary tree node.
class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    if (!preorder.length) return null;
    const val = preorder[0];
    const index = inorder.indexOf(val) + 1;
    const leftPreOrder = preorder.slice(1, index);
    const leftInorder = inorder.slice(0, index - 1);
    const rightPreOrder = preorder.slice(index);
    const rightInorder = inorder.slice(index);
    return new TreeNode(
        val,
        buildTree(leftPreOrder, leftInorder),
        buildTree(rightPreOrder, rightInorder)
    );
};
let map = {}

function build(
    preorder: number[], preStart: number, preEnd: number,
    inorder: number[], inStart: number, inEnd: number,
): TreeNode | null {
    if (preStart > preEnd) {
        return null;
    }
    const val = preorder[preStart];
    const index = inorder.indexOf(val);
    const leftSize = index - inStart;
    const left = build(
        preorder, preStart + 1, preStart + leftSize,
        inorder, inStart, index - 1,
    )
    const right = build(
        preorder, preStart + leftSize + 1, preEnd,
        // inorder, inStart + leftSize + 1, inEnd,
        inorder, index + 1, inEnd,
    )
    return new TreeNode(
        val,
        left,
        right
    );
}
function buildTree1(preorder: number[], inorder: number[]): TreeNode | null {
    inorder.forEach((v,i)=>{
        map[v] = i;
    })
    return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1)
};

console.log(JSON.stringify(buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7]), null, 2))